|
A covering of a polygon is a set of primitive units (e.g. squares) whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered and on the types of units allowed in the covering. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon. In some scenarios, it is not required to cover the entire polygon but only its edges (this is called ''polygon edge covering'') or its vertices (this is called ''polygon vertex covering''). In a covering problem, the units in the covering are allowed to overlap, as long as their union is exactly equal to the target polygon. This is in contrast to a packing problem, in which the units must be disjoint and their union may be smaller than the target polygon, and to a polygon partition problem, in which the units must be disjoint ''and'' their union must be equal to the target polygon. A polygon covering problem is a special case of the set cover problem. In general, the problem of finding a smallest set covering is NP-complete, but for special classes of polygons, a smallest polygon covering can be found in polynomial time. == Basic concepts == A unit ''u'' contained in a polygon ''P'' is called ''maximal'' if it is not contained in any other unit in ''P''. When looking for a polygon covering, it is sufficient to consider maximal units, since every unit which is not maximal can be replaced with a maximal unit containing it without affecting the size of the covering. A ''covering'' of a polygon ''P'' is a collection of maximal units, possibly overlapping, whose union equals ''P''. A ''minimal covering'' is a covering that does not contain any other covering (i.e. it is a local minimum). A ''minimum covering'' is a covering with a smallest number of units (i.e. a global minimum). Every minimum covering is minimal, but not vice versa. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polygon covering」の詳細全文を読む スポンサード リンク
|